package com.datastructure3.stackandqueue;

import com.sun.xml.internal.bind.v2.util.FatalAdapter;
import org.junit.Test;

import java.util.*;

/**
 * @author: 临晖
 * @since: 2024-07-30
 */
public class Solution {

    /**
     * 20. 有效的括号
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        HashMap<Character, Character> map = new HashMap<>();

        //添加括号
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');


        for (int i = 0; i < s.length(); i++) {
            char op = s.charAt(i);
            if (op == '(' || op == '[' || op == '{') {
                stack.push(op);
            } else if (!stack.isEmpty()) {
                if (map.get(stack.peek()) != op) {
                    return false;
                } else {
                    stack.pop();
                }
            } else {
                return false;
            }
        }

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }


    /**
     * 1047. 删除字符串中的所有相邻重复项
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
     * 在 S 上反复执行重复项删除操作，直到无法继续删除。
     * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     *
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        char[] array = s.toCharArray();
        int fast = 0;
        int slow = -1;

        for (; fast < array.length; fast++) {
            if (slow != -1 && array[fast] == array[slow]) {
                slow--;
            } else {
                array[++slow] = array[fast];
            }
        }

        return new String(Arrays.copyOf(array, slow + 1));

    }


    /**
     * 150. 逆波兰表达式求值
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * <p>
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * <p>
     * 注意：
     * <p>
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
     * 两个整数之间的除法总是 向零截断 。
     * 表达式中不含除零运算。
     * 输入是一个根据逆波兰表示法表示的算术表达式。
     * 答案及所有中间计算结果可以用 32 位 整数表示。
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            Integer num = 0;
            if ("+".equals(str)) {
                Integer int1 = stack.pop();
                Integer int2 = stack.pop();
                num = int1 + int2;
            } else if ("-".equals(str)) {
                Integer int1 = stack.pop();
                Integer int2 = stack.pop();
                num = int2 - int1;
            } else if ("*".equals(str)) {
                Integer int1 = stack.pop();
                Integer int2 = stack.pop();
                num = int1 * int2;
            } else if ("/".equals(str)) {
                Integer int1 = stack.pop();
                Integer int2 = stack.pop();
                num = int2 / int1;
            } else {
                num = Integer.parseInt(str);
            }

            stack.push(num);
        }

        return stack.pop();
    }


    /**
     *
     *
     * 239. 滑动窗口最大值
     * 已解答
     * 困难
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回 滑动窗口中的最大值 。
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < k; i++) {

                //6  2  5
                while (!queue.isEmpty() && nums[i] >= queue.getLast()) {
                    queue.removeLast();
                }

                queue.addLast(nums[i]);

        }


        list.add(queue.getFirst());

        for (int i = k; i < nums.length; i++) {
            //移除第一个
            if (nums[i - k] == queue.getFirst()) {
                queue.removeFirst();
            }
            //添加
            while (!queue.isEmpty() && nums[i] > queue.getLast()) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);

            //取最大
            list.add(queue.getFirst());

        }

        int[] res = new int[list.size()];

        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }

        return res;
    }


    /**
     *
     * 347. 前 K 个高频元素
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {

        Arrays.sort(nums);
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });

        //数字，次数

        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                int[] temp = {nums[i - 1], count};
                queue.add(temp);

                if (queue.size() > k) {
                    queue.remove();
                }

                count = 1;
            }
        }

        int[] temp = {nums[nums.length - 1], count};
        queue.add(temp);

        if (queue.size() > k) {
            queue.remove();
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }

        return res;
    }



    @Test
    public void myTest() {
        int[] nums = {1,1,1,2,2,3};
        topKFrequent(nums, 2);
    }

}
